class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        deque<int> q;

        for(int i = 0; i < nums.size(); i++)
        {
            // 1. 入队列     
            // 比如[1, 3, 2, 4, 2, 2, 2]，k = 3
            // 按照这个例子我们可以推演一下
            /*
            比如最开始队列为空，那么1的下标入队列，此时队列为[0, ]
            继续，下一个是3，3比队尾元素还要大，把队尾弹出，此时队列又空了

            再把3的下标入队列，此时队列为[1, ]
            此时只有两个元素比较过了，还差第三个，此时第三个来了，就是2，由于它比队尾元素还要小，它无法成为最大值，所以不能把3弹出，但是能把2入队列，因为2有可能成为后续最大值，所以此时队列为[1, 2]
            然后，此时已经比了三个元素了，可以记录数据了，此时队首就是窗口最大值(后面也是这么保持，一直把队首处理为当前窗口最大值)
            然后，此时4来了，它发现队列不为空，并且还都比他小，那么他就称王了，把前面的3和2都弹出(注意：队列记录的都是下标！)，直到队列为空
            然后4的下标入队列，此时队列为[3, ]
            接着判断4是不是属于当前窗口，执行if(i - q.front() >= k)该语句，发现是3-3 >= 3，条件不满足，所以是当前窗口，不执行pop()
            因为4来了，所以窗口右移了，注意：这里只要最下面的if(i >= k - 1)， 因为这里k是3，所以后面每插入元素都要记录答案的，只有前两次，窗口还不满k
            所以记录4

            此时继续for循环，下一个是2，它比4小，但是有可能成为后续最大值，所以它的下标入队列，队列为[3, 4, ]
            接着继续判断4是不是属于当前窗口，执行if(i - q.front() >= k)该语句，发现是4-3 >= 3，条件不满足，所以是当前窗口，不执行pop()
            继续记录4

            此时继续for循环，下一个是2，它和队尾2相等，有可能成为后续最大值，但是我们这里的逻辑就是把2替换掉了，并且把它的下标入队列，队列为[3, 5, ]
            接着继续判断4是不是属于当前窗口，执行if(i - q.front() >= k)该语句，发现是5-3 >= 3，条件不满足，所以是当前窗口，不执行pop()
            继续记录4

            此时继续for循环，下一个是2，它和队尾2相等，有可能成为后续最大值，但是我们这里的逻辑就是把2替换掉了，并且把它的下标入队列，队列为[3, 6, ]
            接着继续判断4是不是属于当前窗口，执行if(i - q.front() >= k)该语句，发现是6-3 >= 3，条件满足，所以把4终于可以移出去了当前窗口，执行pop()，此时队列变为[6, ]
            然后就是记录队首了，记录下标6对应的元素是2

            至此，遍历结束

            */
            // 如果队列不为空，并且最后一个元素比新来的要小，那这个元素就永远不可能是最大值了。所以直接弹出，弹完之后再把新来的入队列，此时队首就是最大值    
            while(!q.empty() && nums[q.back()] <= nums[i])
                q.pop_back();
            q.push_back(i);
 
            // 2. 出队列
            // 比如[1, 3, 2, 4, 2, 2, 2]
            // 这里指的是队首出队列，因为随着窗口右移，队首可能不会在窗口中了
            if(i - q.front() >= k)
                q.pop_front();
            
            // 3. 记录答案
            // 保持队首始终是当前窗口的最大值
            if(i >= k - 1)
                ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};
    }
};